/* Copyright 2014 Jan Wolter */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void usage(char *progname)
{
    printf("Usage %s [-v] <ranks> <suits>\n", progname);
    exit(1);
}

char *letter= "A23456789TJQK";

void printSoln(int *num, int n, int nc)
{
    for (int i= 0; i < n; i++)
    {
	printf("%c", letter[num[i]]);
    }
    printf(" (%d)\n",nc);
}

#define SUCC(i) (((i)+1)%n)
#define PRED(i) (((i)+n-1)%n)

int verbose= 0, half= 0;
int n= 0, k= 0;
int nsoln= 0;

int main(int argc, char **argv)
{
    int *have, *ends;
    int *num, *changes;

    for (int i= 1; i < argc; i++)
    {
	if (argv[i][0] == '-')
	{
	    for (int j= 1; j < strlen(argv[i]); j++)
		switch (argv[i][j])
		{
		    case 'v': verbose++; break;
		    case 'h': half= 1; break;
		    default: usage(argv[0]);
		}
	}
	else if (n == 0)
	{
	    n= atoi(argv[i]);
	    if (n <= 0) usage(argv[0]);
	}
	else if (k == 0)
	{
	    k= atoi(argv[i]);
	    if (n <= 0) usage(argv[0]);
	}
    }

    if (n == 0 || k == 0)
	usage(argv[0]);

    /* Initialize counts */
    have= (int *) malloc(n * sizeof(int));
    ends= (int *) malloc(n * sizeof(int));
    for (int i= 0; i < n; i++)
    {
	have[i]= k;
	ends[i]= 0;
    }

    /* Always start with Zero */
    int nstep= n * k;
    num= (int *) malloc(nstep * sizeof(int));
    int step= 0;	/* start with step 0 */
    num[step]= 0;	/* step zero is always a zero */
    have[num[step]]--;	/* used up a zero */
    step++;

    /* Initialize our direction change count */
    changes= (int *) malloc(nstep * sizeof(int));
    for (int i= 0; i < nstep; i++)
	changes[i]= 0;

    while (step > 0)
    {
	/* num[0]..num[step-1] is valid.  Add a step */

	/* First try next larger number. */
	int curr= num[step-1];
	if (have[SUCC(curr)] > 0)
	{
	    num[step]= SUCC(curr);
	    have[num[step]]--;
	    step++;
	}
	/* Otherwise try next lower number */
	else if (have[PRED(curr)] > 0)
	{
	    num[step]= PRED(curr);
	    have[num[step]]--;
	    step++;
	}
	/* Otherwise we are at dead end */
	else
	{
	    if (step == nstep)
	    {
		/* Count direction changes */
		int nc= 0;
		for (int i= 1; i < nstep-1; i++)
		    if (num[i-1] == num[i+1]) nc++;
		changes[nc]++;

		/* Found a valid sequnce */
		if (verbose) printSoln(num, nstep, nc);
		nsoln++;
		ends[num[step-1]]++;
	    }

	    /* Backtrack */
	    while (--step > 0)
	    {
		have[num[step]]++;
		if (num[step] == SUCC(num[step-1]) &&
			have[PRED(num[step-1])] > 0
			&& (!half || step > 1))
		{
		    /* Went forward before but could go back.  Do that. */
		    num[step]= PRED(num[step-1]);
		    have[num[step]]--;
		    step++;
		    break;
		}

	    }
	}

    }
    if (half) printf("Did Half\n");
    printf("%d Sequences Found\nLast Card:\n", nsoln);
    for (int i= 0; i < n; i++)
	printf("  %c: %d\n",letter[i], ends[i]);
    printf("Direction Changes:\n");
    int maxc;
    for (maxc= nstep - 1; maxc > 0 && changes[maxc] == 0; maxc--)
	;
    for (int i= 0; i <= maxc; i++)
	printf("  %3d: %d\n",i, changes[i]);
}
